// Tim kiem bang phuong phap chia doi - nhi phan
#include <iostream>
using namespace std;
int search ( int x, int *mang, int begin, int end ){
	int ava = ( begin + end) / 2;
	if ( mang[ava] == x ) return 1;
	if ( ava == begin || ava == end ) return 0;
	if ( mang[ava] < x) search (x, mang, ava, end); // xet nua ben phai
	else search (x, mang, begin, ava);	// xet nua ben trai
}

int main(){
	int n;
	cout << "So phan tu: ";
	cin >> n;
	int *mang;
	mang = new int [n];
	cout << "Nhap day so tang dan" << endl;
	for ( int i = 0; i < n; i++){
		cout << "Phan tu thu " << i + 1 << ":";
		cin >> mang[i];
	}
	int x;
	cout << "Tim so:";
	cin >> x;
	int begin = 0;
	int end = n - 1;
	if ( search (x, mang, begin, end)) cout << "Trong day co gia tri " << x;
	else cout << "Trong day khong co gia tri " << x;
	cout << endl;
	system("pause");
	return 0;
}